#include <stdio.h>

/*
	 采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。
	 
	 例如，a[1]=5，表示在棋盘的第例的第五行放一个皇后。程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，
	 
	 然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。
 */

#define Q   8

int queen[Q + 1];

int main()
{
    int i, k, flag, not_finish = 1, count = 0;

    i = 1; // 正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素
    queen[1] = 1; // 为数组的第一个元素赋初值

    printf("The possible configuration of 8 queens are:\n");

	printf("%d:queen[%d] = %d\n",  __LINE__, i, queen[i]);
    while (not_finish) {
        while (not_finish && i <= Q) { // 处理尚未结束且还没处理到第Queens个元素
            for (flag = 1, k = 1; flag && k < i; k++) { // 判断是否有多个皇后在同一行
				printf("\t\tqueen[k=%d] = %d, queen[i=%d] = %d\n", k, queen[k], i, queen[i]);
                if (queen[k] == queen[i])	// 不能出现相同的数字.因为是一组数组,以k作为行,queen[i]为列
                    flag = 0;
			}
            

            for (k = 1; flag && k < i; k++) { // 判断是否有多个皇后在同一对角线
				printf("\t\t\t\tqueen[i=%d] = %d, queen[k=%d] = %d, queen[k]-(k-i) = %d, queen[k]+(k-i) = %d\n", 
					i, queen[i], k, queen[k], queen[k] - (k - i), queen[k] + (k - i));
									// 左上到右下						// 右上到左下
                if ((queen[i] == queen[k] - (k - i)) || (queen[i] == queen[k] + (k - i)))
                    flag = 0;
			}
            

            if (!flag) { // 若存在矛盾不满足要求，需要重新设置第i个元素
                if (queen[i] == queen[i - 1]) { // 若a[i]的值已经经过一圈追上a[i-1]的值
                    i--;  // 退回一步，重新试探处理前一个元素

                    if (i > 1 && queen[i] == Q)
                        queen[i] = 1;           // 当a[i]为Queens时将a[i]的值置1
                    else if (i == 1 && queen[i] == Q) 
                        not_finish = 0;         // 当第一位的值达到Queens时结束; 退出整个循环,只运行一次.
                    else 
                        queen[i]++;             // 将a[i]的值取下一个值
                }
                else if (queen[i] == Q)
                    queen[i] = 1;
                else
                    queen[i]++;                 // 将a[i]的值取下一个值
            }
            else if (++i <= Q) {
				printf("%d:queen[%d] = %d\n",  __LINE__, i, queen[i]);
                if (queen[i - 1] == Q) {
                    queen[i] = 1;               // 若前一个元素的值为Queens则a[i]=l
					printf("%d:queen[%d] = %d\n", __LINE__, i, queen[i]);
				}
                else { 
                    queen[i] = queen[i-1]+1;    // 否则元素的值为前一个元素的下一个值
					printf("%d:queen[%d] = %d\n", __LINE__, i, queen[i]);
				}
			}
        }

        if (not_finish) {
            ++count;
            //printf((count - 1) % 3 ? "\t[%2d]:" : "\n[%2d]\n", count);
			printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count);

            for (k = 1; k <= Q; k++)   // 输出结果
                printf(" %d", queen[k]);

            if (queen[Q-1] < Q)
                queen[Q-1]++;   // 修改倒数第二位的值
            else
                queen[Q-1] = 1;

            i = Q - 1;    // 开始寻找下一个满足条件的解 
        }
    }
	printf("\n");
}
